package com.aqie.medium.dynamicProgram;

import java.util.HashMap;

/**
 * 494 目标和 todo
 */
public class FindTargetSumWays {
    /**
     * 1.动态规划
     * @param nums
     * @param S
     * @return
     */
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < S || (sum + S) % 2 == 1) {
            return 0;
        }
        int w = (sum + S) / 2;
        int[] dp = new int[w + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = w; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[w];
    }


    /**
     * 2.DFS
     * @param nums
     * @param S
     * @return
     */
    public int findTargetSumWays2(int[] nums, int S) {
        return findTargetSumWays(nums, 0, S, 0);
    }

    private int findTargetSumWays(int[] nums, int index, int S, int sum) {
        int res = 0;
        if (index == nums.length) {
            return sum == S ? ++res : res;
        }
        res += findTargetSumWays(nums, index + 1, S, sum + nums[index]);
        res += findTargetSumWays(nums, index + 1, S, sum - nums[index]);
        return res;
    }

    /**
     * 3.记忆化搜索
     */
    private HashMap<Integer, Integer>[] map;
    private int findWays(int[] nums, int S, int index) {
        if (index >= nums.length)
            if (S == 0)
                return 1;
            else
                return 0;
        if (map[index].containsKey(S))
            return map[index].get(S);
        int res = 0;
        res += findWays(nums, S + nums[index], index + 1);
        res += findWays(nums, S - nums[index], index + 1);
        map[index].put(S, res);
        return res;
    }

    public int findTargetSumWays3(int[] nums, int S) {
        if (nums == null || nums.length == 0)
            return 0;
        map = new HashMap[nums.length];
        for (int i = 0; i < map.length; i++)
            map[i] = new HashMap<>();
        return findWays(nums, S, 0);
    }
}
